#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void insertion(int *arry, int size)
{
  int i, j, next;

  printf("sorting list...\n");

  for (i=1; i<size; i++)
  {
     next = arry[i];
     
	 for(j=i; j>0 && next < arry[j-1]; j--)      
        arry[j] = arry[j-1];

     arry[j] = next;
  }
}
void merge(int *arry, int first, int last)
{
	int i= first;
	int j= last;
	
	for (int k=first; k<last; k++)
	{
		if(arry[i]<arry[j])
		{
			arry[k]= arry[i];
			i++;
		}
		else
		{
			arry[k]= arry[j];
			j++;
		}
	}
}


void mergeSorting(int *arry, int first, int last)
{
	int middle = (first + last)/2;

	if(last<=0) return;

	mergeSorting(arry,first,middle);
	mergeSorting(arry,middle+1,last);
	merge(arry,first,last);

}

void printList(int *arry, int size)
{
	for(int i=0; i<size; i++)
	{
		printf("%d\n",arry[i]);
	}

}

void main()
{
	int size=0;
	int *arry;


	printf("enter list size: ");
	scanf("%d",&size);

	arry = (int *)malloc(size*sizeof(int));


	for(int i = 0; i<size; i++)
	{
		arry[i]= rand()%size;
		
	}



	clock_t start = clock();
	insertion(arry,size);
	//mergeSorting(arry,1,size);
	clock_t finish = clock();

	printList(arry,size);
	


	double sec = (finish-start)/(double)CLOCKS_PER_SEC;
	printf("%f\n",sec);


}